{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Subsequence With Limited Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #binary-search #prefix-sum #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #二分查找 #前缀和 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: answerQueries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #和有限的最长子序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为 <code>n</code>&nbsp;的整数数组 <code>nums</code> ，和一个长度为 <code>m</code> 的整数数组 <code>queries</code> 。</p>\n",
    "\n",
    "<p>返回一个长度为 <code>m</code> 的数组<em> </em><code>answer</code><em> </em>，其中<em> </em><code>answer[i]</code><em> </em>是 <code>nums</code> 中<span style=\"\"> </span>元素之和小于等于 <code>queries[i]</code> 的 <strong>子序列</strong> 的 <strong>最大</strong> 长度<span style=\"\">&nbsp;</span><span style=\"\"> </span>。</p>\n",
    "\n",
    "<p><strong>子序列</strong> 是由一个数组删除某些元素（也可以不删除）但不改变剩余元素顺序得到的一个数组。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [4,5,2,1], queries = [3,10,21]\n",
    "<strong>输出：</strong>[2,3,4]\n",
    "<strong>解释：</strong>queries 对应的 answer 如下：\n",
    "- 子序列 [2,1] 的和小于或等于 3 。可以证明满足题目要求的子序列的最大长度是 2 ，所以 answer[0] = 2 。\n",
    "- 子序列 [4,5,1] 的和小于或等于 10 。可以证明满足题目要求的子序列的最大长度是 3 ，所以 answer[1] = 3 。\n",
    "- 子序列 [4,5,2,1] 的和小于或等于 21 。可以证明满足题目要求的子序列的最大长度是 4 ，所以 answer[2] = 4 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,3,4,5], queries = [1]\n",
    "<strong>输出：</strong>[0]\n",
    "<strong>解释：</strong>空子序列是唯一一个满足元素和小于或等于 1 的子序列，所以 answer[0] = 0 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>m == queries.length</code></li>\n",
    "\t<li><code>1 &lt;= n, m &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= nums[i], queries[i] &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-subsequence-with-limited-sum](https://leetcode.cn/problems/longest-subsequence-with-limited-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-subsequence-with-limited-sum](https://leetcode.cn/problems/longest-subsequence-with-limited-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,5,2,1]\\n[3,10,21]', '[2,3,4,5]\\n[1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        sz1 = len(nums)\n",
    "        sz2 = len(queries)\n",
    "        nums.sort()\n",
    "        for i in range(1, sz1):\n",
    "            nums[i] += nums[i - 1]\n",
    "        return [bisect_right(nums, i) for i in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        for i, q in enumerate(queries):\n",
    "            ret = 0\n",
    "            j = 0\n",
    "            while j < len(nums):\n",
    "                num = nums[j]\n",
    "                if ret + num <= q:\n",
    "                    ret += num\n",
    "                    j += 1\n",
    "                else:\n",
    "                    break\n",
    "            queries[i] = j\n",
    "        return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        res=[]\n",
    "        n=len(nums)\n",
    "        for i in range(len(queries)):\n",
    "            sub=0\n",
    "            k=-1\n",
    "            for j in range(n):\n",
    "                sub+=nums[j]\n",
    "                if sub>queries[i]:\n",
    "                    k=j\n",
    "                    break\n",
    "                elif sub==queries[i]:\n",
    "                    k=j+1\n",
    "                    break\n",
    "            else:\n",
    "                k=n\n",
    "            res.append(k)\n",
    "        return res\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        f = list(accumulate(sorted(nums)))\n",
    "        return [bisect_right(f, q) for q in queries]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "\n",
    "        # 对nums排序 依次从小到大求前缀和\n",
    "        nums = sorted(nums)\n",
    "        \n",
    "        prefix = []\n",
    "        presum = 0\n",
    "        for numi in nums:\n",
    "            presum += numi\n",
    "            prefix.append(presum)\n",
    "\n",
    "        print(prefix)\n",
    "\n",
    "        # 对每个query循环 直到找到大于query的元素\n",
    "        ans = []\n",
    "\n",
    "        for query in queries:\n",
    "            ind = 0\n",
    "            while ind < len(nums) and prefix[ind] <= query:\n",
    "                ind += 1\n",
    "            ans.append(ind)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums = sorted(nums)\n",
    "        queries = sorted([x, i] for i,x in enumerate(queries))\n",
    "        ans = []\n",
    "        ni = qi = s = 0\n",
    "        while qi < len(queries):\n",
    "            if ni >= len(nums) or queries[qi][0] < s + nums[ni]:\n",
    "                print(s, ni)\n",
    "                ans.append(ni)\n",
    "                qi += 1\n",
    "            else:\n",
    "                s += nums[ni]\n",
    "                ni += 1\n",
    "        return [x[1] for x in sorted([(i, x) for (_, i), x in zip(queries, ans)])]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        ans = []\n",
    "        n = len(nums)\n",
    "        for i in queries:\n",
    "            j = 0\n",
    "            s = 0\n",
    "            a = 0\n",
    "            while j < n:\n",
    "                s += nums[j]\n",
    "                if s <= i:\n",
    "                    a = j + 1\n",
    "                    j += 1\n",
    "                else:\n",
    "                    break\n",
    "            ans.append(a)\n",
    "        return ans\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        nums.sort()\n",
    "        for i in range(len(queries)):\n",
    "            tem = 0\n",
    "            ci = 0\n",
    "            for j in range(len(nums)):\n",
    "                if tem+nums[j]<=queries[i]:\n",
    "                    tem+=nums[j]\n",
    "                    ci+=1\n",
    "            res.append(ci)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        m = len(queries)\n",
    "        nums.sort()\n",
    "        answers = [0] * m\n",
    "        pre_sum = [0]\n",
    "        for i,num in enumerate(nums):\n",
    "            pre_sum.append(pre_sum[-1] + num)\n",
    "\n",
    "        for i in range(m):\n",
    "            answers[i] = bisect.bisect(pre_sum,queries[i]) - 1\n",
    "        return answers\n",
    "                \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
